/*************************MemoryRewriteChecker.h****************************
 * @file MemoryRewriteChecker.h                                            *
 * @author Comphsics                                                       *
 * @date 2021.2.2                                                          *
 * @details                                                                *
 *     This file implements memory rewrite checker which is a              *
 *     interprocedural analysis                                            *
 ***************************************************************************/
#ifndef MEMORYREWRITECHECKER_H
#define MEMORYREWRITECHECKER_H
#include <vector>
#include <memory>
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/PointerIntPair.h"
#include "clang/Basic/Diagnostic.h"
#include "clang/Basic/DiagnosticIDs.h"
#include <tuple>
#include <list>
#include "framework/VariableAnalyzer.h"
#include "framework/BasicChecker.h"
#include "framework/Report.h"
#include "llvm/ADT/DenseMap.h"

class MemoryRewriteChecker;
class MemoryRewriteAnalyzer;

namespace MRDetail{
    /// READ: Read
    /// PARTIALLYREAD: partially read(no write)
    /// WRITE: Write
    /// PARTIALLYWRITE: partially write(no read)
    /// READWRITE: both read and write
    /// PARTIALLYREADWRITE: both read and write and no access

    // using hexadecimal digits:
    //   ------partial write read----
    //   ------ 0      0     1   ----    READ
    //   ------ 0      1     0   ----    WRITE
    //   ......
    enum class StatusType:unsigned char{
        READ=0x001,PARTIALLYREAD=0x005,WRITE=0x002
        ,PARTIALLYWRITE=0x006,READWRITE=0x003,PARTIALLYREADWRITE=0x007
    };

    /// @brief The status of a symbol of one flow.
    /// The FirstStatus records the first status in a flow,
    /// The LastStatus records the last status in a flow.
    struct SymbolStatus{
        StatusType FirstStatus;
        StatusType LastStatus;
        SymbolStatus()=default;
        SymbolStatus(const SymbolStatus& Right){
            FirstStatus=Right.FirstStatus;
            LastStatus=Right.LastStatus;
        }
    };
    struct Operation{
        Operation(){
            Op=nullptr;
        }
        Operation(const Operation&Other){
            Op=Other.Op;
            Id=Other.Id;
            Read=Other.Read;
        }
        Operation(const Operation&&Other){
            Op=Other.Op;
            Id=Other.Id;
            Read=Other.Read;
        }
        const clang::Expr *Op;
        size_t Id;
        bool Read;
    };
    class SymbolPool{
        friend class ::MemoryRewriteAnalyzer;
    private:
        using SymbolExprType=std::list<Operation>;
        llvm::DenseMap<Symbol::SymbolType *,SymbolExprType> Pool;
        /// insert new data.
        void insert(Symbol::SymbolType*ST,size_t Id,const clang::Expr*E,bool Read);
        void insert(Symbol::SymbolType*ST,size_t Id,const std::vector<const clang::Expr*>& Es,bool Read);
        /// set RightId to LeftId.
        void replace(Symbol::SymbolType *ST,size_t LeftId,size_t RightId);
        void replace(Symbol::SymbolType *ST,size_t LeftId,size_t RightId,bool Read);
        /// update the Symbol,if finding a pair<ST,Id> remove it,
        /// finally insert the new data;
        void update(Symbol::SymbolType*ST,size_t Id,const clang::Expr*E,bool Read);
        void update(Symbol::SymbolType*ST,size_t Id,const std::vector<const clang::Expr*>& Es,bool Read);
        /// remove all Id's expr.
        void remove(Symbol::SymbolType *ST,size_t Id);
        void remove(Symbol::SymbolType *ST,size_t Id,bool Read);

        std::vector<const clang::Expr*> getExprs(Symbol::SymbolType *ST,size_t Id);
        std::vector<const clang::Expr*> getExprs(Symbol::SymbolType *ST,size_t Id,bool Read);

        /// merge RightId to LeftId. Note this will hold the RightId, but add all RightId's exprs
        ///     to LeftId.
        void merge(Symbol::SymbolType *ST,size_t LeftId,size_t RightId);
        void merge(Symbol::SymbolType *ST,size_t LeftId,size_t RightId,bool Read);

    };
    class Flow{
    private:
        friend class ::MemoryRewriteAnalyzer;
        llvm::DenseMap<Symbol::SymbolType*,SymbolStatus> Content;
        /// using Other's symbols to update this.
        /// @note Always update the Last Status
        void updateWith(Flow *Other);
        /// @brief merge the flow.
        /// @details This method is called when exiting an IfStmt,
        ///      The IfStmt may have an else or not. 
        void mergeWith(Flow* Else=nullptr);
    };
}
class MemoryRewriteAnalyzer final:public VariableAnalyzer{
private:
    friend class MemoryRewriteChecker;
    /// @brief When this is true, do not report memory-rewrite on simple
    ///		variables
    bool DisableSimpleVariable;
    /// @brief When this is true, the first rewrite operation is 
    ///	not overlapped by the second.
    bool Overlap;

    struct PatchInfo 
    {
        std::vector<const clang::Expr*> Previous;
        std::vector<const clang::Expr*> After;
        const clang::VarDecl* Variable;
    };
    
    std::vector<PatchInfo*> Patches;

    // must hold only one Pool object. 
    std::unique_ptr<MRDetail::SymbolPool> Pool;
    std::stack<std::tuple<const clang::Stmt*,int,bool>> FlowStack;

    std::stack<MRDetail::Flow*> PreFlows;
    std::stack<MRDetail::Flow*> ThenFlows;
    MRDetail::Flow *MainFlow;

    /// @detail 
    /// This static method is used to store a pointer and a bit value,
    /// the bit value means the first or last status on the flow.
    /// we use llvm::PointerIntPair to encrypt the flow.
    /// and the returned value will set to <code>Id</code> 
    /// of type <code>Operation</code>
    static size_t computeEncryptedValue(MRDetail::Flow *Flow,bool First){
        llvm::PointerIntPair<MRDetail::Flow*,1> Tmp(Flow,First?1:0);
        return reinterpret_cast<size_t>(Tmp.getOpaqueValue());
    }
    
    /// @brief Records all global symbol statuses of a function.
    ///     Used to check interprocedural memory rewrite warnings.
    llvm::DenseMap<const clang::FunctionDecl*,MRDetail::Flow*> FunctionFlows;
    const clang::FunctionDecl *CurrentFunction{};
    MRDetail::Flow* findFlowOfFunction(const clang::FunctionDecl *FD) const {
        auto It=FunctionFlows.find(FD);
        if(It!=FunctionFlows.end()){
            return It->getSecond();
        }else{
            return nullptr;
        }
    }
    /// merge Else to Then
    void mergeFlow(MRDetail::Flow* Then,MRDetail::Flow* Else=nullptr);

    /// update After to Before,
    /// when Hold is true,will not modify any symbols of After in Pool,
    /// otherwise, all symbols of After will update to Before
    void checkAndUpdateFlow(MRDetail::Flow* Before,MRDetail::Flow* After,bool Hold);
    void checkAndUpdateSymbol(MRDetail::Flow* Current,Symbol::SymbolType*ST,const clang::Expr*E,bool Read);
    void checkTopSymbol(Symbol::SymbolType*ST,const clang::Expr *E,bool Read);
    void checkElementSymbol(Symbol::SymbolType *ST,const clang::Expr *E,bool Read);
    /// @brief If the <code>ST</code> is record or array,
    ///     returns true if some of its elements (recursively) 
    ///     is written last status, otherwise returns false.
    bool checkElementSymbolWrite(Symbol::SymbolType *ST,std::vector<const clang::Expr*>&ElementExprs);
    void checkElementSymbolRead(Symbol::SymbolType*ST,const clang::Expr*E);
    PatchInfo* convertToPatch(Symbol::SymbolType*ST,size_t After,size_t Before);
    PatchInfo* convertToPatch(Symbol::SymbolType*ST,size_t Before);
    
    
    /// @brief Check if redundancy occurs in uncertain symbol of an array
    ///		or in pointee symbol of a pointer.
    bool occursNotInUncertainOrPointeeSymbol(const Symbol::SymbolType*ST);
    // FIXME: complete check rewrite operation on alias.
    bool checkAliasRedundancy(const Symbol::SymbolType *ST);

protected:
    // a set of overriden methods

    void enterFunctionScope(const FunctionDecl*FD) override;

    void enterIfScope(const clang::IfStmt *IS)override;

    void enterElseScope(const clang::IfStmt *IS) override;


    void enterSwitchScope(const clang::SwitchStmt*SS)override;
    
    void enterCaseScope(const clang::CaseStmt*CS)override;

    void enterDefaultScope(const clang::DefaultStmt*DS)override;


    void enterCallExpr(const clang::CallExpr *CE) override;

    void finishScope(Footprints *FP)override;

    void visitSymbol(Symbol::SymbolType *ST,bool Read,const clang::Expr*E)override;

    void visitSymbolAddress(Symbol::SymbolType*ST,const clang::Expr*E)override;

    int getCountOfLoopStmt(const clang::ForStmt *FS) override;
public:
    explicit MemoryRewriteAnalyzer(const clang::ASTContext *AC) : VariableAnalyzer(AC) {
        MainFlow=nullptr;
        DisableSimpleVariable=false;
        DefaultLoopCount=1;
        Overlap=true;
        Pool=std::make_unique<MRDetail::SymbolPool>();
    }
    ReportSpace::Defect* convertToReport(PatchInfo *Patch);
    void reportToConsole(PatchInfo *Patch);

};
class MemoryRewriteChecker: public BasicChecker{
private:
    std::vector<MemoryRewriteAnalyzer*> Checkers;
    IgnLibPathConfig IgnorePaths;
public:
    void addSingleChecker(MemoryRewriteAnalyzer *C){
        Checkers.push_back(C);
    }
    MemoryRewriteChecker(ASTResource *resource, ASTManager *manager, CallGraph *callGraph, Config *configure)
            : BasicChecker(resource, manager, callGraph, configure) {

    }
    void readConfig(MemoryRewriteAnalyzer *Analyzer);

    void check();
};
#endif